package com.cat.graphTheory;

import java.util.*;

/**
 *   @description https://leetcode.cn/problems/loud-and-rich/
 *   @author 曲大人的喵
 *   @create 2025/9/25 18:48
 *   @since JDK17
 */

public class Solution35 {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[]g = new List[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        int[] ans = new int[n], in = new int[n];
        for (var e : richer) {  // 建图
            g[e[0]].add(e[1]);
            in[e[1]]++;
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                q.add(i);
            }
            ans[i] = i;
        }

        while (!q.isEmpty()) {
            var p = q.pollFirst();
            for (int e : g[p]) {    //
                if (quiet[ans[p]] < quiet[ans[e]]) {
                    ans[e] = ans[p];
                }
                if (--in[e] == 0) { // 入度为零
                    q.add(e);
                }
            }
        }

        return ans;
    }
}
